接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

![leetcode 接雨水](leetcode 接雨水.png)

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

1
2
输入：height = [4,2,0,3,2,5]
输出：9

提示：

  • n == height.length
  • 0 <= n <= 3 * 104
  • 0 <= height[i] <= 105

代码：

100%90%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
    public int trap(int[] height) {
        int n=0;
        int begin=-1;
        int end=-1;
        for(int i=0;i<height.length;i++)
        {
            if(begin==-1&&height[i]!=0)
            {
                begin=i;
            }
            if(begin!=-1)
            {
                end=-1;
                int index=-1;
                int max=-1;
                //寻找后面有没有大于等于begin的，顺便找后面最大的值与坐标
                for(int j=i+1;j<height.length;j++)
                {
                    if(height[j]>=height[begin])
                    {
                        end=j;break;
                    }
                    if(height[j]>max)
                    {
                        max=height[j];
                        index=j;
                    }
                }
                //如果存在，则将i-j之间的所有数填满至最小的，，begin=j，将i移动到j，并将j重置成-1
                if(end!=-1)
                {
                    int temp=Math.min(height[begin],height[end]);
                    for(int j=begin;j<end;j++)
                    {
                        n+=temp-height[j];
                        height[j]=temp;
                    }
                    begin=end;
                    i=end-1;
                }
                //如果不存在，则i为目前最高，则直接到后面最高的，填至min（【i】，【max】），i移动到max，
                else if(index!=-1)
                {

                    int temp=Math.min(height[begin],max);
                    for(int j=begin;j<=index;j++)
                    {
                        if(temp>height[j])
                        {
                            n+=temp-height[j];
                            height[j]=temp;
                        }
                    }
                    begin=index;
                    i=index-1;
                }

            }
        }
        return n;
    }
}